给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数  。

你可以对一个单词进行如下三种操作：

插入一个字符

删除一个字符

替换一个字符

示例 1：

输入：word1 = "horse", word2 = "ros"

输出：3

解释：

horse -> rorse (将 'h' 替换为 'r')

rorse -> rose (删除 'r')

rose -> ros (删除 'e')

let minDistence = function (word1, word2) {

  let dp = Array.from(Array(word1.length + 1), () => Array(word2.length + 1).fill(0))

  for (let i = 1; i <= word1.length; i++) {

    dp[i][0] = i

  }

  for (let j = 1; j <= word2.length; j++) {

    dp[0][j] = j

  }

  for (let i = 1; i <= word1.length; i++) {

    for (let j = 1; j <= word2.length; j++) {

      if (word1[i - 1] === word2[j - 1]) dp[i][j] = dp[i - 1][j - 1]

      else dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1)

    }

  }

  return dp[word1.length][word2.length]

}

  

console.log(minDistence('horse', 'ros'))

动态规划

建立数组




只有三种情况 绿色：增
红色：删
黄色：改 取最小的步骤放在结果

dp[i][j] 表示 word1 的前 i 字符和 word2 前 j 字符通过最简单的步骤已经转换成一样的了

填表填到 dp[len word1][len word2] 就是最终结果